/**
 *  dc.cpp; compiled by VC++6.0
 *  divide-conquer, compute the nearest pair of points
**/

#include <stdio.h>
#include <stdlib.h>
#include  "math.h"

/**
*struct node, to store the vertice in the graph
**/
struct Node
{
  int x;
  int y;
};
/**struct Dist
* for return, store the distance and nodes adjacent to it
**/
struct Dist
{
	Node start;
	Node end;
	double value;
};
int first_L;// the value of first L
/**initG()
*to init the input graph
**/
void initG(Node *g,int n)
{
	g[0].x=31;
	g[0].y=0;
	g[1].x=48;
	g[1].y=0;
    g[2].x=37;
	g[2].y=8;
	g[3].x=43;
	g[3].y=9;
    g[4].x=30;
	g[4].y=13;
	g[5].x=38;
	g[5].y=20;
	g[6].x=42;
	g[6].y=19;
	g[7].x=50;
	g[7].y=25;
    g[8].x=39;
	g[8].y=30;
	g[9].x=41;
	g[9].y=30;
	g[10].x=36;
	g[10].y=40;
	g[11].x=46;
	g[11].y=40;
	g[12].x=47;
	g[12].y=75;
	g[13].x=40;
	g[13].y=50;
	g[14].x=49;
	g[14].y=55;
    g[15].x=34;
	g[15].y=60;
	g[16].x=33;
	g[16].y=70;
    g[17].x=44;
	g[17].y=65;
	g[18].x=0;
	g[18].y=5;
	g[19].x=10;
	g[19].y=4;
	g[20].x=17;
	g[20].y=40;
    g[21].x=5;
	g[21].y=50;
	g[22].x=12;
	g[22].y=60;
	g[23].x=60;
	g[23].y=1;
	g[24].x=65;
	g[24].y=14;
	g[25].x=69;
	g[25].y=55;
	g[26].x=74;
	g[26].y=43;
    g[27].x=78;
	g[27].y=2;
}
void 
merge (Node *A, int a, Node *B, int b, Node *C,int direct) 
{
  int i,j,k;
  i = 0; 
  j = 0;
  k = 0;
  while (i < a && j < b) {
	  if(direct==0){
    if (A[i].x <= B[j].x) {
	  /* copy A[i] to C[k] and move the pointer i and k forward */
	  C[k] = A[i];
	  i++;
	  k++;
    }
    else {
      /* copy B[j] to C[k] and move the pointer j and k forward */
      C[k] = B[j];
      j++;
      k++;
	  }
	  }
	  else
		  {
    if (A[i].y <= B[j].y) {
	  /* copy A[i] to C[k] and move the pointer i and k forward */
	  C[k] = A[i];
	  i++;
	  k++;
    }
    else {
      /* copy B[j] to C[k] and move the pointer j and k forward */
      C[k] = B[j];
      j++;
      k++;
	  }
	  }
  }
  /* move the remaining elements in A into C */
  while (i < a) {
    C[k]= A[i];
    i++;
    k++;
  }
  /* move the remaining elements in B into C */
  while (j < b)  {
    C[k]= B[j];
    j++;
    k++;
  }
}  

/**
 * merge_sort()
 * Sort array A with n integers, using merge-sort algorithm.
 **/
void 
merge_sort(Node *g, int left,int right,int direct) 
{
  int i;
  Node *A1, *A2;
  int n=right-left+1;
  int n1, n2;

  if (n < 2)
    return;   /* the array is sorted when n=1.*/
  
  /* divide A into two array A1 and A2 */
  n1 = n / 2;   /* the number of elements in A1 */
  n2 = n - n1;  /* the number of elements in A2 */
  A1 = (Node*)malloc(sizeof(Node) * n1);
  A2 = (Node*)malloc(sizeof(Node) * n2);
  
  /* move the first n/2 elements to A1 */
  for (i =0; i < n1; i++) {
    A1[i] = g[i];
  }
  /* move the rest to A2 */
  for (i = 0; i < n2; i++) {
    A2[i] = g[i+n1];
  }
  /* recursive call */
  merge_sort(A1, 1,n1,direct);
  merge_sort(A2,1,n2,direct);

  /* conquer */
  merge(A1, n1, A2, n2, g,direct);
  free(A1);
  free(A2);
}
/**Swap()
*swap two elements in the vector
**/
void Swap(Node *node,int a,int b)
{
	Node temp;
    temp=node[a];
	node[a]=node[b];
	node[b]=temp;
}
/**
 * Partion() 
 *partion elements between low and high in the vector
 **/
int Partion(Node *g,int low, int high,int direct)
{
	int pos=low;
	Node p=g[low];
	for(int i=low+1;i<=high;i++){
		if(direct==0){
			if(g[i].x<p.x&&++pos!=i){
				 Swap(g,pos,i);
			}
		}
		else{
		  if(g[i].y<p.y&&++pos!=i){
				 Swap(g,pos,i);
			}
		}
	}
	Swap(g,low,pos);
	return pos;
}  

/**
 * quick_sort()
 * if direct=0,sort the input nodes from left to right by x coordinate value
 * if direct=1,sort the input nodes from left to right by y coordinate value
 **/
void 
quick_sort(Node *g, int left,int right,int direct) 
{
 if(left<right){
   int pos;
   
   pos=Partion(g,left,right,direct);  
   quick_sort(g,left,pos-1,direct);
   quick_sort(g,pos+1,right,direct);
 }
}
/** distance()
* To compute the distance between two nodes
**/
double distance(Node a,Node b)
{
	int x1,x2,y1,y2;
	double dist;
	x1=a.x;
	y1=a.y;
	x2=b.x;
	y2=b.y;
	dist=sqrt(pow(x2-x1,2)+pow(y2-y1,2));
	return dist;
}
/**compute()
* To calculate the minimum distance of a small graph
**/
Dist compute(Node *g,int n)
{
	Dist d;
	double temp;
	double init_v;
	int i=0;
	int j=0;

    d.start=g[0];
    d.end=g[1];
    init_v=distance(g[0],g[1]);
    d.value=init_v;

	for (i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			temp=distance(g[i],g[j]);
			if(temp<d.value){
				d.value=temp;
				d.start=g[i];
				d.end=g[j];
			}		
		}
	}
	return d;
}
/**find_mini()
*find the smaller value
**/
Dist find_mini(Dist m,Dist n)
{
	if(m.value<=n.value)
		return m;
    return n;
}

/**min()
*compare two numbers,return the smaller one
**/
int min(int a,int b)   
{   
    if(a<=b)   
        return a;   
    return b;   
}   

/**combine()
* scan the nodes within distance d of line L,combine the result
**/
Dist combine(Node *g,Dist di,int L,int num,Node *gy)
{
	Node *new_g;
	double temp;
    double d;
	int index;
	int sign;
	int i;
	Dist current_d;

	current_d.value=di.value;
	current_d.start=di.start;
	current_d.end=di.end;

	new_g = (Node *)malloc(sizeof(Node) * num);

	d=di.value;
	index=0;
	for(int j=0;j<num;j++){
		if(L-d<=gy[j].x&&gy[j].x<=L+d){
	    	new_g[index]=gy[j];	
			index++;
        }		  
	}
	//  at this step, the value of index is equal to the number of nodes in new_g
	
//	if(L==first_L){
	    printf("sorted by y coordinate for those nodes within d of L\n");
		printf("------------------------------\n");
		for (i = 0; i < index; i++){
			printf("     (%d, %d)", new_g[i].x,new_g[i].y);
			printf("\n");
		}
		printf("------------------------------\n");
//	}//print the nodes  related in the last combine

   	for(int k=0;k<index;k++){
		sign=0;
		for(int l=k+1;l<min(k+12,index);l++){
		    temp=distance(new_g[k],new_g[l]);
			if(L==first_L){
				if(sign==0){
					printf("compare pair of nodes:  ");
					sign=1;
				}
				printf(" (%d, %d) <--%.2f--> (%d,%d) ", new_g[k].x,new_g[k].y,temp,new_g[l].x,new_g[l].y);
			    if(l<min(k+12,index)-1){
					printf(",");				
				}
			}// print the procedure of last combine
			if(temp<d){
				current_d.value=temp;
				current_d.start=new_g[k];
				current_d.end=new_g[l];
				d=temp;
			}		
		}
	   if(L==first_L){
			printf("\n");
		}
	}
	free(new_g);
    return current_d;
}
/**Mini_dist()
*Mini_dist, computer the mimimum distance between two nodes in the graph, 
*using divide-conquer algorithm
**/
Dist Mini_dist(Node *g,int n,Node *gy)
{
	int i;
	Dist mini;
	Dist d;
	Node *g1, *g2;
    Node *gy1, *gy2;
	Dist d1,d2;
    int L;
	int n1;
	int n2;
	int index1;
	int index2;
	if(n<5)//The number of nodes is small, then we can calculate the minimum distance in
		   //a constant time.
	{	
		 d=compute(g,n);
		 printf("------------------------------\n");
         printf("compute: \n");
         for (i = 0; i < n; i++) {
           printf("(%d, %d)", g[i].x,g[i].y);
           printf("\n");
		 }
         return d;
	}

    /* divide g into two array g1 and g2 by the x coordinate divide_x*/
	/*select line L, so that there are roughly 1/2 points on each side*/
    n1 = n / 2;   /* the number of elements in g1 */
    n2 = n - n1;  /* the number of elements in g2 */
	L=g[n1-1].x;
    g1 = (Node*)malloc(sizeof(Node) * n1);
    g2 = (Node*)malloc(sizeof(Node) * n2);
    gy1 = (Node*)malloc(sizeof(Node) * n1);
    gy2 = (Node*)malloc(sizeof(Node) * n2);  
	
	/* move the first n/2 elements to g1 */
     for ( i =0; i < n1; i++) {
       g1[i] = g[i];
	 }
    /* move the rest to g2 */
    for ( i = 0; i < n2; i++) {
        g2[i] = g[i+n1];
	}
    
	index1=0;
	index2=0;

	for(i=0;i<n;i++){
		if(gy[i].x<L){
			gy1[index1]=gy[i];
			index1++;
		}
		if(gy[i].x==L)
		{
			if(gy[i].y<=g[n1-1].y)
			{
					gy1[index1]=gy[i];
			        index1++;
			}
			else
			{
					gy2[index2]=gy[i];
					index2++;			
			}
		}
		if(gy[i].x>L){
			gy2[index2]=gy[i];
			index2++;
		}
	}

	/* recursive call */

   d1=Mini_dist(g1, n1,gy1);

   printf("----------------------\n");
   printf("d1.value = %.2f", d1.value);
   printf("\n");
   printf("----------------------\n");

   d2=Mini_dist(g2, n2,gy2);

   printf("----------------------\n");
   printf("d2.value = %.2f", d2.value);
   printf("\n");
   printf("----------------------\n");

   /* conquer */

   mini=find_mini(d1, d2);
	
   printf("\n");
   printf("------combine--------");
   printf("----------------------\n");


   d=combine(g,mini,L,n,gy);
     
   free(g1);
   free(g2);
   free(gy1);
   free(gy2);
   return d;
    
}
/**
 *  main()
 *  The main function for input and output 
 **/
void
main(int argv, char** args)
{

	Node *g; 
	Node *g_sorted_by_y;
	int i;
	Dist dist;
    int size;//size of the input graph
   
	size=28;

    g = (Node *)malloc(sizeof(Node) * size);
    g_sorted_by_y = (Node *)malloc(sizeof(Node) * size);
	
   	initG(g,size);



	printf("\n");
	printf("************** Input **************\n");
	printf("\n");
    printf("------------------------------\n");

    printf("The input graph is: \n");
    for (i = 0; i < size; i++) {
      printf("(%d, %d)", g[i].x,g[i].y);
      printf("\n");
	}
    printf("------------------------------\n");
    merge_sort(g,0,size-1,1);
   	merge_sort(g,0,size-1,0);
		for(i=0;i<size;i++){
		g_sorted_by_y[i].x=g[i].x;
	    g_sorted_by_y[i].y=g[i].y;
	}
	merge_sort(g_sorted_by_y,0,size-1,1);

	first_L=g[size/2-1].x;

    printf("\n");
    printf("************** Sorted **************\n");
    printf("\n");
    printf("------------------------------\n");

    printf("Sort the graph by x coordinate: \n");
    for (i = 0; i < size; i++){
      printf("(%d, %d)", g[i].x,g[i].y);
      printf("\n");
	}
    printf("------------------------------\n");

    printf("------------------------------\n");
    printf("Sort the graph by y coordinate: \n");
    for (i = 0; i < size; i++){
      printf("(%d, %d)", g_sorted_by_y[i].x,g_sorted_by_y[i].y);
      printf("\n");
	}
    printf("------------------------------\n");
	printf("\n");

	printf("************** Process **************\n");

	dist=Mini_dist(g,size,g_sorted_by_y);

    printf("----------------------\n");
	printf("\n");
	printf("mini.value = %.2f", dist.value);
    printf("\n");
    printf("----------------------\n");
	printf("\n");	
	printf("\n");
    printf("************** Result **************\n");
    printf("\n");
    printf("------------------------------\n");
    printf("The Closest Pair of Points is:   ");
    printf("(%d, %d)", dist.start.x,dist.start.y);
    printf(" <--> ");
    printf("(%d, %d)", dist.end.x,dist.end.y);
    printf("\n");
    printf("The distance is: %.2f\n", dist.value);
    printf("------------------------------\n");

    free(g);
	free(g_sorted_by_y);
    printf("Press any key to continue");
    getchar();
}